package zuo.middleLevel_6;

import tools.Tree.Tree;

import java.util.TreeMap;

/**
 * @Author: Forx
 * @Data: 2021/6/25
 * @Desc: Algorithm - zuo.middleLevel_6
 * @Version: v1.0
 */
public class ML6 {
    /**
     * 字符串只由'0'和'1'两种字符构成，
     * 当字符串长度为1时，所有可能的字符串为"0"、"1";
     * 当字符串长度为2时，所有可能的字符串为"00"、"01"、"10"、"11";
     * 当字符串长度为3时，所有可能的字符串为"000"、"001"、"010"、"011"、"100"、
     * "101"、"110"、"111"
     * 如果某一个字符串中，只要是出现'0'的位置，左边就靠着'1',这样的字符串叫作达
     * 标字符串。
     * 给定一个正数N,返回所有长度为N的字符串中，达标字符串的数量。
     * 比如，N=3,返回3,因为只有"101"、"110"、"111"达标。
     *
     * n=1 ans=1;
     * n=2 ans=2;
     * n=3 ans=3;
     * ...
     * [1....]共有i+1个字符
     * 令f(i)=f(n-1),因为第一位必须是1
     * 1右边的第一位有两种可能,如果填1的话那就是fi-1
     * 如果填0那么下一个字符必须是1,那就是fi-2
     * 因此
     * fi = fi-1+fi-2
     * 因此
     * fi+1 = fi+fi-1
     * [fi+1,fi] = [fi,fi-1]*[{1,1},{1,0}]
     * 因此就可以快速的算出来fi
     *
     * */
    /**
     * 在迷迷糊糊的大草原上，小红捡到了n根木棍，第i根木棍的长度为i,
     * 小红现在很开心。想选出其中的三根木棍组成美丽的三角形。
     * 但是小明想捉弄小红，想去掉一些木棍，使得小红任意选三根木棍都不能组成
     * 三角形。
     * 请问小明最少去掉多少根木棍呢？
     * 给定N,返回至少去掉多少根？
     *
     * 假如n=17,答案就是17以内的斐波那契数列(除去第一个1)为保留项,
     *
     * */
    /**
     * 牛牛准备参加学校组织的春游，出发前牛牛准备往背包里装入一些零食，牛牛的背包容
     * 量为w。
     * 牛牛家里一共有n袋零食，第i袋零食体积为v[i]。
     * 牛牛想知道在总体积不超过背包容量的情况下，他一共有多少种零食放法（总体积为0也
     * 算一种放法）。
     *
     * 动态规划
     *
     * 要与不要
     * */
    /**
     * 按照层级输出目录
     * a/b/c a/b/d
     * 输出
     * a
     *  b
     *    c
     *    d
     * */
    public static class dirs{
        private String[] processStrings;
        public static class Node {
            public String name;
            public TreeMap<String,Node> map;

            public Node(String name) {
                this.name = name;
                map = new TreeMap<>();
            }
        }

        public static Node generalPrefixTree(String[] dirs){
            Node head = new Node("");
            for(String str:dirs){
                String[] nams = str.split("\\\\");
                Node cur = head;
                for(String name:nams){
                    if(!cur.map.containsKey(name)){
                        cur.map.put(name,new Node(name));
                    }
                    cur = cur.map.get(name);
                }
            }
            return head;
        }
        public static String generalSpace(int level){
            int cnt = level*2;
            StringBuilder ans = new StringBuilder();
            for (int i = 0; i < cnt; i++) {
                ans.append("-");
            }
            return ans.toString();
        }
        public static void printProcess(Node head,int level){
            if(head==null){
                return;
            }
            System.out.println(generalSpace(level)+head.name);
            for(Node node : head.map.values()){
                printProcess(node,level+1);
            }
        }

    }
    /**
     * 在一棵二叉树中找到符合搜索二叉树并且包含节点数量最多的子树
     * */
    public static class findMaxSunBT{
        public static class Node {
            public Node left;
            public Node right;
            public int val;

            public Node(int val) {
                this.val = val;
                left = null;
                right = null;
            }
        }
        public static class Info {
            private int size;
            private boolean isBT;
            public Node min;
            public Node max;
            private Node curMax;

            private Info(int size, boolean isBT, Node min, Node max, Node curMax) {
                this.size = size;
                this.isBT = isBT;
                this.min = min;
                this.max = max;
                this.curMax = curMax;
            }
        }

        public static Node solution(Node root){
            Info info = process(root);
            return info.curMax;
        }
        private static Info process(Node node){
            if(node==null){
                return null;
            }
            Info leftInfo = process(node.left);
            Info rightInfo = process(node.right);
            if(leftInfo==null && rightInfo==null){
                return new Info(1,true,node,node,node);
            }else if(leftInfo==null){
                if(rightInfo.isBT && rightInfo.min.val >= node.val){
                    return new Info(rightInfo.size+1,true,node,rightInfo.max,node);
                }else {
                    return new Info(rightInfo.size,false,node,rightInfo.max,rightInfo.curMax);
                }
            }else if(rightInfo==null){
                if(leftInfo.isBT && leftInfo.max.val <= node.val){
                    return new Info(leftInfo.size+1,true,leftInfo.min,node,node);
                }else {
                    return new Info(leftInfo.size,false,leftInfo.min,node,leftInfo.curMax);
                }
            }else {
                if(rightInfo.isBT && leftInfo.isBT && leftInfo.max.val <= node.val && rightInfo.min.val >=node.val){
                    return new Info(leftInfo.size+rightInfo.size+1,true,leftInfo.min,rightInfo.max,node);
                }else {
                    if(leftInfo.size > rightInfo.size){
                        return new Info(leftInfo.size,false,leftInfo.min,leftInfo.max,leftInfo.curMax);
                    }else {
                        return new Info(rightInfo.size,false,rightInfo.min,rightInfo.max,rightInfo.curMax);
                    }
                }
            }

        }
        public static void solutionVerify(){
            Node root = new Node(3);
            Node node1 = new Node(5);
            Node node2 = new Node(7);
            Node node3 = new Node(1);
            Node node4 = new Node(6);
            Node node5 = new Node(4);
            Node node6 = new Node(8);
            Node node7 = new Node(2);
            Node node8 = new Node(2);
            Node node9 = new Node(10);
            Node node10 = new Node(9);
            Node node11 = new Node(1);
            root.left = node1;
            root.right = node2;
            node1.left = node3;
            node1.right = node4;
            node3.right = node7;
            node2.left = node5;
            node2.right = node6;
            node5.left = node8;
            //node5.right = node9;
            node8.left = node11;
            node6.right = node10;

            Node ans = solution(root);
        }
    }
    /**
     * 给定一个矩阵怎么获得最大的子行列式的累加和
     * */
    public static class da{


    }

    public static void main(String[] args) {
//        String[] osdirs = {
//                "a\\b\\c",
//                "a\\b\\d",
//                "c\\e\\f\\g\\h",
//                "c\\e\\f\\g\\h1",
//                "c\\e\\f\\g\\h2",
//                "c\\e\\f1\\g\\h2",
//                "c\\e\\f1\\g\\h2",
//                "c\\e1\\f\\g\\h2",
//        };
//        dirs.Node head = dirs.generalPrefixTree(osdirs);
//        dirs.printProcess(head,0);
        findMaxSunBT.solutionVerify();

    }




}
